# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        visited = set()
        s = []
        s.append(root)
        output = []

        while (s):
            top = s[-1]
            while (top.left and top.left not in visited):#注意两个while循环嵌套！！！！
                s.append(top.left)
                top = top.left
            if top.left is None or top.left in visited:
                if top.right is None or top.right in visited:
                    q = s.pop()
                    visited.add(q)
                    output.append(q.val)
                elif top.right and top.right not in visited:
                    s.append(top.right)
        return output


